Binary Search Trees: Core Operations

Binary Search Trees (BST): The Ordering Invariant

The Binary Search Tree structure is fundamental because it imposes a strict ordering invariant on all nodes, enabling efficient search and insertion.

$$\text{Left Subtree Value} < \text{Root Value} < \text{Right Subtree Value}$$

Searching and Insertion Mechanics

Both searching for a key $K$ and inserting a new node follow the same pathfinding logic starting from the root:

1. Comparison: Compare $K$ to the Current Node's value.
2. Path Selection: If $K < \text{Current Node}$, move Left (L); if $K > \text{Current Node}$, move Right (R).
3. Termination (Search): Stop when the node is found or when a NULL pointer is reached (key not present).
4. Termination (Insertion): The new node is attached at the final NULL position found.

This directed traversal ensures that, in a balanced tree, the maximum number of comparisons needed is $O(\log n)$.

Successor & Predecessor: Key to Deletion

Finding the in-order Successor (the node with the next largest key) is essential for the deletion algorithm when the node to be removed has two children.

1. If node $N$ has a Right Child: The successor is the minimum value in the right subtree. Move one step Right, then continuously follow Left pointers.
2. If node $N$ has NO Right Child: The successor is the nearest ancestor $A$ for which $N$ is in $A$'s left subtree.

Performance Characteristics: $O(\log n)$ vs. $O(n)$

BSTs provide logarithmic performance only if the tree remains relatively balanced. If data is inserted in sorted order, the tree degenerates into a skewed list, resulting in worst-case linear time complexity.

Operation	Average Case (Balanced)	Worst Case (Skewed)
Search	$O(\log n)$	$O(n)$
Insertion	$O(\log n)$	$O(n)$
Deletion	$O(\log n)$	$O(n)$
Finding Successor	$O(\log n)$	$O(n)$